#include <stdio.h> 
#include <stdlib.h>  
#include <math.h>  
#include <queue> //
#include <vector>//
#define INF (0x23333333)//  
#define MAXN (302)  //
using namespace std;
//寻四方向用  
 
  
int map[MAXN][MAXN]; //地图  
int n=20;
int m=20;   //地图的行数列数  
int g[MAXN][MAXN]; //已用代价，参数为行列坐标  
int h[MAXN][MAXN]; //估计还需代价，参数为行列坐标  
 
struct point  
{  
    int l,c;  
    point(){}  
    point(int _l, int _c){l=_l;c=_c;}  
    bool operator<(const point &o) const  
    {  
        return g[l][c]+h[l][c]>g[o.l][o.c]+h[o.l][o.c];  
        
    }  
};

vector<point> find_path(int sl,int sc,int tl,int tc)  
{  
    
int i,j; 
    int	l,c;
    int cl,cc,nl,nc;
    //int tl,tc,sl,sc;  
    const int dl[] = {1,-1,0,0};  
    const int dc[] = {0,0,-1,1}; 
	bool in_close[MAXN][MAXN]; 
    bool in_open[MAXN][MAXN]; 
    point path[MAXN][MAXN];    	
     	
    priority_queue<point> open_list;
     vector<point>	pth;
	 vector<point> pthTemp;
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      path[i][j]=point(i,j);//初始化路径
    
   for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	 		 in_close[i][j] = false;  //初始化关闭列表
	
	pth.clear(); //清空路径列表	 
    
    
    for(i = 1; i <= n; i++)  
    {  
        for(j = 1; j <= m; j++)  
        {  
            h[i][j] = (int)sqrt((double)(i-tl)*(i-tl)+(double)(j-tc)*(j-tc))+1;  //估计代价 = 这个点到目标点的几何距离向上取整  
            g[i][j] = INF; //已用代价初始化为INF  
        }  
    }   
      
    //出发点扔到open_list  
    g[sl][sc] = 0;  
    in_open[sl][sc] = true;  
    open_list.push(point(sl,sc));  
      
    while(open_list.size())  
    {  
        cl = open_list.top().l;  
        cc = open_list.top().c;  
        open_list.pop();  
        if(cl == tl && cc == tc)         
            break;  
        
        //当前点算入关闭列表中  
        in_close[cl][cc] = true;  
        for(i = 0; i < 4; i++)  
        {  
            nl = cl+dl[i];  
            nc = cc+dc[i];  
            if(map[nl][nc] !=0)continue; //不可通行  
            if(in_close[nl][nc])continue; //在关闭列表  
            if(! in_open[nl][nc])  
            {  
                open_list.push(point(nl,nc));  
            }else if(g[cl][cc]+1 >= g[nl][nc])  
                continue;   
            path[nl][nc] = point(cl,cc);  
            g[nl][nc] = g[cl][cc] + 1;  
        }  
    } 
	 l = tl;  
     c = tc; 
	while(true)
    {
		//map[l][c] =1;
		pth.push_back(point(l,c));
		if(l == sl && c == sc)
			break;  
       i = path[l][c].l;  
       j = path[l][c].c;  
        l = i;  
        c = j; 
        
	}
	for(i=0;i<pth.size();i++)
		       pthTemp.push_back(pth[pth.size()-i-1]);
		   pth=pthTemp;
	return pth;
	
}  

void print_res()  
{  
	
    int i,j;     
    
    for(i = 0; i <= n+1; i++)  
    {  
        for(j = 0; j <= m+1; j++)  
        {  
            switch(map[i][j])
            {
            	case 0:printf("  ");break;
            	case 1:printf("\033[31m\033[43m1 \033[m");break;
            	case 2:printf("\033[31m\033[43m2 \033[m");break;
            	case 3:printf("\033[31m\033[43m3 \033[m");break;
            	case 4:printf("\033[31m\033[43m4 \033[m");break;
            	case 5:printf("\033[31m\033[43m5 \033[m");break;
            	case 6:printf("\033[36m\033[44mA \033[m");break;
            	case 7:printf("\033[36m\033[44mB \033[m");break;
				case 8:printf("\033[36m\033[44mC \033[m");break;
				case 9:printf("\033[36m\033[44mD \033[m");break;
				case 10:printf("\033[36m\033[44mE \033[m");break;
				case 11:printf("* ");break;
            	default:break;
            	} 
        }  
        putchar('\n');  
    }  		
	
      
}  


void IniMap()
{
	 int i, j; 
    for(i = 0; i <= n+1; i++)  
        for(j = 0; j <= m+1; j++)  
            map[i][j] = 11;     
    for(i = 1; i <= n; i++)  
        for(j = 1; j <= m; j++)  
             map[i][j] =0;
    for(i=0;i<80;i++)
           map[rand()%(n-2)+2][rand()%(m-2)+2]=11;
     	   
	
}

int main()  
{  
int i,j;
   
  vector<point> m_pth;
  
   IniMap();
   m_pth.clear();
   m_pth=find_path(1,1,n,m);
     for(vector<point>::iterator iter=m_pth.begin();iter!=m_pth.end();iter++)
		 map[(*iter).l][(*iter).c]=1;
    print_res();
	 
    return 0;  
}





























































































